package jianzhiOfferII;

import java.util.ArrayList;
import java.util.List;

//剑指 Offer II 027. 回文链表
public class Num027_isPalindrome {
    public boolean isPalindrome(ListNode head) {
        ListNode mid = mid(head);
        ListNode re = reverse(mid);
        return isPalindromeHelper(head , re);
    }

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null)return head;
        ListNode newNode = new ListNode(0 );
        ListNode sc = head.next;
        newNode.next = reverse(head.next);
        sc.next = head;
        head.next = null;
        return newNode.next;
    }

    public ListNode mid(ListNode head){
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast !=null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;

    }
    public boolean isPalindromeHelper(ListNode head , ListNode mid){
        while (mid != null){
            if (mid.val != head.val)return false;
            head = head.next;
            mid = mid.next;
        }
        return true;

    }

//    public boolean isPalindrome(ListNode head) {
//        List<Integer>list = new ArrayList<>();
//        while (head != null){
//            list.add(head.val);
//            head = head.next;
//        }
//        int l = 0;
//        int r = list.size() - 1;
//        while (l < r){
//            if (list.get(l) != list.get(r)){
//                return false;
//            }
//            l++;
//            r--;
//        }
//        return true;
//
//    }
}
